My above-referenced U.S. patent application Ser. No. 757,091, filed Sep. 10, 1991, now abandoned, entitled "Method and Apparatus for Spatially Variant Filtering," describes a selective/adaptive filtering mechanism, which is based upon image activity within spatial windows surrounding pixels of an image to be processed, as a new and improved solution of (texture) image spatial filtering which remedies the problem of prior art approaches, which exclusively use either low-pass spatial filtering or high-pass spatial filtering.
As pointed out in that application, although the prior art techniques of using only low-pass filtering to reduce differences between individual pixel values and the general pixel-value levels in their neighborhoods tends to reduce the effects of noise and the visibility of "jaggies" that result from spatial quantization, it also undesirably tends to blur images and thus reduce the sharpness that is more desirable for textual-type images. High-pass filtering, on the other hand, operates to increase differences between a pixel value and the general level in its surrounding neighborhood. While this tends to lend desirable sharpness to textual images, it also amplifies noise and thereby makes "snow" in solid areas more noticeable.
In accordance with the selective/adaptive filtering scheme described in my above-identified '091 application, now abandoned, the type of filtering to be employed is not limited to only lowpass or only highpass processing. It is adaptively dependent upon the level of variation in the image. Pursuant to my selective, adaptive filtering approach, a variation window is associated with each pixel, and the variation in input pixel values associated with the pixels in that variation window is computed. For each of a plurality of pixels in the image, a `selective` filtering process choice is made between performing and refraining from performing one of a high-pass and a low-pass operation. The process choice depends upon the variation computed for that pixel. Then, in accordance with the process choice, pixel output values are generated by performing high-pass or low-pass filtering on some of the input pixel values but not performing it on others. This selective high-pass, low-pass filtering has been found to greatly enhance the readability of the processed image.
FIG. 1 diagrammatically illustrates depicts a digital image processing system as described in the above-referenced '091 application for recording in a memory 12 or displaying on a display device 14 the contents of an image source such as a microfilm strip 16. Microfilm strip 16 may be illuminated by a light source 18 and the illuminated image scanned by a digitizing scanner 20. Scanner 20 includes circuitry that treats the resultant image as being divided into a plurality or array of pixels, and it generates digital image signals representing digitized values of those pixels as `raw pixel-value` digital input signals for application to downstream digital image processing components, including an adaptive filter 24 and a quantizer 22, prior to storage or display. Display device 14 may comprise one of a number of display device types, such as a cathode-ray tube or image-applying machinery contained in a photocopier.
In accordance with the invention described in the '091 application, now abandoned, adaptive filter 24 is operative to selectively perform one of high-pass and low-pass spatial filtering on respective pixels of the digitized image prior to quantizing. In order to determine which type of filtering is to be selectively used, the respective pixels of the digitized image are initially classified in accordance with their relative values and the value variations in surrounding neighborhoods.
More specifically, with reference to FIG. 2, associated with each pixel in the digitized image, such as the central pixel 26, are two surrounding neighborhoods or `windows` of pixels. A first, larger window 28 is preferably sized to be about half the extent of the significant part of the imaging system's point-source function, i.e., of the light-intensity function that results from a single point source in the plane of the microfilm. The contents of this larger window are used to establish an average value Ma of the values of all pixels within the window. Although this average may be a weighted average in which the pixels closer to the central pixel 26 are weighted more heavily, a straight average, in which all pixels are equally weighted, is preferred. This average value Ma is employed as a threshold between those pixel values that are considered to be background and those pixel values that are considered to convey signal (character) information, as will be described.
To determine whether the pixel 26 is within a background region or is within a signal region, the large-window neighborhood average Ma is compared with a local average Mb computed over a second, smaller window 30 surrounding pixel 26. Window 30 may be of any smaller size; in principle, in fact, it can be so small as to include only pixel 26. For noise-suppression purposes, however, window 30 preferably contains a plurality of pixels.
In addition to large window average Ma and smaller window, or local, average Mb, two further parameters are employed to classify a pixel. One of these is an "activity level" parameter Md, which is a measure of the variation in pixel value in a window around the +pixel 26 under consideration. For the sake of convenience, the larger window 28 that is used to compute Ma is employed to calculate Md. However, such a choice is not necessary.
The variation or activity level Md may be computed in any number of ways, such as standard deviation or absolute mean. In the preferred embodiment, the absolute mean deviation, defined as follow is employed: ##EQU1##
where Pij is the value of the jth pixel in the ith row, K and L are the width and height, respectively, of the window over which the variation is computed, Mw is an average pixel value in that window (and is equal to Ma in the illustrated embodiment), and the upper-left-corner pixel in that window is the xth pixel in the yth row.
Which filter operation is to be performed by adaptive filter 24 is determined by: 1) comparing the small-window average Mb with the large-window average Ma; and 2) comparing the activity level Md with an `activity threshold value` MD.sub.-- THR, which is intended to approximate the general variation level in the image as a whole. The manner in which MD.sub.-- THR is determined is described in detail below.
FIG. 3 depicts the manner in which the four parameters Ma, Mb, Md and MD.sub.-- THR are employed to classify an input pixel Pi. The abscissa is the smaller-window average Mb, while the ordinate is the activity level Md. If Mb is less than the product of some constant k1 and the larger-window average Ma, then the pixel of interest is considered to be associated with a (no signal) background region 31, and its output value Po is computed in accordance with the following function: EQU Po=Pi-A1 Ma-Mb , (2)
where Po is the output pixel value, Pi is the input pixel value, and A1 is an independent reduction factor--a constant (which may be equal to 0). If a pixel lies is the background region 31, the application of equation (2) tends to drive the pixel value farther into the background region. That is, in the case of a typical microfilm image, where the lighter areas (which, in this case, have lower numerical values) represent background, the processing of pixels by equation (2) causes light valued background pixels to become even lighter in the output image.
On the other hand, if the local window average Mb associated with the input pixel value Pi is larger than a second constant k2 times the larger-window average Ma, namely the pixel of interest is associated with a potential signal region 32, then that pixel's output or replacement value Po depends on what the activity level Md is around that pixel. If the activity level Md associated with the pixel of interest is greater than the general activity threshold level MD.sub.-- THR, then the input pixel Pi is considered to be representative of signal and the value of the pixel is updated or replaced in accordance with the following equation: EQU Po=Pi+A2 Ma-Mb , (3)
where A2 is an independent constant gain factor (which may be equal to zero). Typically, the same constants are used for reduction factor A1 and gain factor A2, but this is not necessary.
Reflection reveals that the processing of an input pixel value in accordance with either of equations (2) and (3) has the effect of applying a high-pass function to the pixel value. Namely, equations (2) and (3) tend to amplify any differences between individual pixel values and the surrounding average. On the other hand, if a pixel whose smaller window average Mb exceeds k2Ma, so that it falls within region 32, but is associated with a window whose variation Md is less than the variation threshold MD.sub.-- THR, the adaptive filter performs a low-pass function; that is, it replaces the input pixel value Pi with the smaller-window average Mb, which operation tends to smooth the image and de-emphasize differences between pixel values.
FIG. 3 also depicts a region 33 between Mb=k1Ma and Mb=k2Ma, which is to be subjected to a low-pass filtering operation. In region 33, in which the small-window average Mb is nearly equal to the large-window average Ma, there is essentially no general image variation around the pixel, and any significant difference between the particular pixel value under consideration and the values of the surrounding pixels should be suppressed. As a practical matter, k1 and k2 are set by the system quantization error; that is, the region between Mb=k1Ma and Mb=k2Ma represents that the local window average Mb is equal to the larger window average Ma to within the quantization error of the signal processing. (While one might similarly consider reserving for separate treatment a horizontal small-difference region around Md=MD.sub.-- THR like the vertical region around Mb=Ma, I have found no particular advantage for such an scheme.) It should also be recognized that the high- and low-pass filtering equations (2) and (3) are merely exemplary, and others may be used. On the right side of equations (2) and/or (3), for example, Pi could be replaced with Mb--or vice versa--and similar (although not identical) results would be obtained.
The manner in which the activity threshold MD.sub.-- THR may be computed is set forth in the flow chart of FIG. 4. As pointed out above, the activity threshold MD.sub.-- THR is intended to approximate the general variation level ( or, in some embodiments, some fraction or multiple of it, perhaps with a constant added or subtracted ) in the image as a whole. Although the most accurate way to determine its level would require two passes through the image, speed as well as cost considerations in some applications make a two-pass process undesirable. As a result, a further aspect of the invention described in the above-referenced '091 application, now abandoned, involves executing an `on-the-fly` routine that iteratively adjusts the activity threshold level MD.sub.-- THR as processing of the digitized image proceeds.
The overall approach illustrated in FIG. 4 is to maintain a single value for the activity threshold MD.sub.-- THR throughout an entire scan line of the digitized image array, and then automatically update the MD.sub.-- THR value it at the end of the scan line in accordance with an interim variation-indicating value IMG.sub.-- MD, that is iteratively adjusted on a pixel-by-pixel basis from the beginning of a respective line to the end of that line. The routine so varies IMG.sub.-- MD during the line scan that the value of IMG.sub.-- MD tends toward an average of the variations in the windows of those pixels whose window variations exceed an `average low spatial frequency activity` level PREV.sub.-- MD, which the routine has identified as being the average variation in certain low-spatial-frequency regions of the image.
At the beginning of each image, a first step or block 40 of process of FIG. 4 initializes the activity threshold MD.sub.-- THR, as well as the two variable levels IMG.sub.-- MD and PREV.sub.-- MD, and a third value BG.sub.-- MD, associated with a temporary low frequency activity level, which is used to update PREV.sub.-- MD at the end of a line. In the illustrated process, a non-limitative choice of eight-bit resolution yields a pixel-value range of 0-255. It may be observed that the process of FIG. 4 departs from the usual flow-chart convention by depicting two parts of the routine operating in parallel.
One portion of the routine, which will be described below, begins with decision step 42, while the other portion, which is employed to establish the average activity level (i.e., variation) PREV.sub.-- MD in low-frequency regions, begins with another decision block 44. Like the activity threshold MD.sub.-- THR, PREV.sub.-- MD is updated only at the end of each scan line. In the interim, a temporary value BG.sub.-- MD, from which PREV.sub.-- MD is updated, as described above, is adjusted by the part of the FIG. 4 routine that starts with step 44.
Step 44 identifies pixels that are most likely to be in low-spatial-frequency regions. For this purpose, step 44 employs as a criterion the equality of (actually, less than a quantization-error difference between) Ma and Mb, i.e., between the larger- and smaller-window averages. If the pixel under consideration meets this criterion, then the temporary low frequency activity level BG.sub.-- MD is adjusted up or down slightly toward the activity level Md within that particular pixel's larger window.
Specifically, if decision step 46 determines that BG.sub.-- MD exceeds Md, then BG.sub.-- MD is decremented or decreased by 1/100 of its value in step 48. Thus step 48 must be repeated one hundred times to change BG.sub.-- MD by one unit at the pixel-value resolution. If the value of BG.sub.-- MD does not exceed Md, it is incremented or increased by 1/100 in step 50. Such an adjustment of BG.sub.-- MD occurs for every pixel that meets the criterion of step 44. At the end of a respective scan line, the average low-frequency-region activity-level value PREV MD is updated in step 52 to the current value of BG.sub.-- MD. This average low frequency activity level value PREV.sub.-- MD is used in the first step 42, of the other parallel routine.
Decision step 42 compares the current pixel's activity level Md with the low-frequency-region activity level PREV.sub.-- MD. If the current pixel's activity level Md is not at least equal to that low-frequency-region activity level PREV.sub.-- MD, then the value of the variation within the current pixel's window will not be used to affect the activity threshold MD.sub.-- THR, and the process proceeds to step 62. Otherwise, the temporary-value variable IMG.sub.-- MD, from which the activity-level threshold MD.sub.-- THR is updated, is adjusted slightly up or down toward the variation Md within the current pixel's window, as shown by steps 54, 56, and 60.
At the end of a scan line (decision step 62), the activity threshold MD.sub.-- THR is adjusted in accordance with the equation of step 64. As shown in step 64, the activity threshold MD.sub.-- THR is essentially adjusted half way from its previous value (at the end of the previous line) to the current value of IMG.sub.-- MD at the end of the current line. (The "bias" represented by the "+1" in the equation of step 64 is used only to overcome an artifact of the limited-precision arithmetic used in the calculation.)
FIG. 5 is a diagrammatic illustration of a non-limitative example of signal processing circuitry that may be employed to implement the digital image signal processing routine described above in real time. A line store 66 receives the raw pixel values from the scanning device and accumulates the pixel values in a group of scan lines equal in number to the height of the larger windows. At the pixel-scan rate, it applies to average-computing circuits 68 and 70 a window's worth of pixel values for the large and small windows, respectively. These circuits compute Ma and Mb, which they apply to a subtraction circuit 72. Circuit 72 sends the magnitude part of the result--i.e., the absolute value--to two multipliers 74 and 76, which receive the high-pass-equation constants A1 and A2 from appropriate registers not shown in the drawings. The values used for these constants are not critical. A value of eight has been satisfactorily employed for both constants in a system in which the pixel values are given with eight-bit resolution.
Adders 78 and 80 respectively subtract and add these values from and to the input pixel value for the pixel currently under consideration and apply the results to a three-input multiplexer 82. At the same time, a variation-calculating circuit 84 uses the output of the line store 66 and the Ma value from averaging circuit 68 to compute the variation Md in the larger window's pixel values. From this and the line-store output, it also generates the activity threshold MD.sub.-- THR. On the basis of the resulting MD.sub.-- THR and Md values and of an output of subtraction circuit 72 that indicates whether Mb is greater than, equal to, or less than Ma, a classifier 86 classifies the current pixel in accordance with the FIG. 3 scheme and applies to multiplexer 82 a select signal that represents the FIG. 3 class to which the pixel currently under consideration belongs. Multiplexer 82 then selects among the (low-pass) Mb value from the averaging circuit 70 and the two high-pass-filter outputs from adders 78 and 80 to produce the proper replacement pixel value. As pointed out in my earlier filed '091 application, in the embodiment illustrated in FIG. 5, classifier 86 may additionally supply its output to quantizer 22, if that quantizer is of the type described in my co-pending U.S. patent application Ser. No. 757091, filed Sep. 10, 1991, now abandoned, for "Spatially Variant Filtering System," assigned to the assignee of the present application and the disclosure of which is herein incorporated.
Although the above-described selective/adaptive filtering mechanism of my co-pending '091 application, now abandoned, offers a significantly improvement over prior art approaches of exclusively using either low-pass spatial filtering or highpass spatial filtering to process digital images, I have developed modifications that may be incorporated in the highpass filter and activity level thresholding mechanisms of the system, which enable the adaptive filter to provide a still further enhanced output digital image.